package algorithm.AC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class AC {

    public static class Node {
        private String end;
        private boolean endUse;
        private Node fail;
        private Node[] next;

        public Node() {
            end = null;
            endUse = false;
            fail = null;
            next = new Node[26];
        }

    }

    public static class TrieTree {
        private Node root;

        public TrieTree() {
            root = new Node();
        }

        public void insert(String str) {
            char[] chars = str.toCharArray();
            Node node = root;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if (node.next[index] == null)
                    node.next[index] = new Node();
                if (i == chars.length - 1) {
                    node.next[index].end = str;
                }
                node = node.next[index];
            }
        }

        //不走一些路（最长来保证），少走一些路（前后缀相等的部分）
        public void build() {//父节点的fail到的节点已经是最长的了，而子节点时在父节点的基础上fail的，自然也是最长的
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                Node father = queue.poll();
                for (int i = 0; i < father.next.length; i++) {
                    if (father.next[i] != null) {
                        Node tmp = father.fail;
                        while (tmp != null && tmp.next[i] == null)
                            tmp = tmp.fail;
                        father.next[i].fail = tmp == null ? root : tmp.next[i];
                        queue.add(father.next[i]);
                    }
                }
            }
        }

        public Node getRoot() {
            return root;
        }
    }

    public static class MyAC {
        private TrieTree tree;

        public MyAC(String[] arr) {
            tree = new TrieTree();
            for (String s : arr) {
                tree.insert(s);
            }
            tree.build();
        }

        //与kmp的整体思路相似，可以前缀树的作用（寻找最长的相等前后缀的分支）看成kmp中next数组的作用
        public List<String> containWords(String content) {
            if(content == null || content.length() == 0)
                return null;
            char[] str = content.toCharArray();
            ArrayList<String> res = new ArrayList<>();
            Node root = tree.root;
            Node cur = root;
            int i = 0;
            while (i < str.length) {
                if (cur.next[str[i] - 'a'] != null) {//如果前缀树的当前节点有这条路就沿着这个分支走下去
                    cur = cur.next[str[i] - 'a'];
                    Node node = cur;
                    //需要判断当前节点与他fail到的节点是不是一个字符串的最后一个字符，是的话就收集
                    while (node != root) {
                        if(node.endUse == true)
                            break;
                        if (node.end != null){
                            res.add(node.end);
                            node.endUse = true;
                        }
                        node = node.fail;
                    }

                    i++;
                } else if (cur == root) {//表示文章中当前位置的字符与前缀树中的所有的第一个字符都不匹配时，
                                         //在寻找最长前缀的过程中但凡匹配上一个都会fail到那里。
                    i++;
                } else {
                    cur = cur.fail;//去找与当前节点后缀长度"最长"相等的前缀的对应位置
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        String[] arr = {"dhe", "he", "abcdheks", "sb"};
        String content = "abdhekskdjfabcdfhasldkflskdjhwqaeruv";
        MyAC myAC = new MyAC(arr);
        List<String> list = myAC.containWords(content);
        System.out.println(list);
    }
}
